This invention relates generally to modulation coding of data, and more particularly to input partitioning in modulation coding systems, together with corresponding decoding systems.
Modulation codes are employed in data storage systems to eliminate undesirable bit-sequences in the recording data, for example bit sequences which give rise to errors in the reproduction process. One example of an undesirable bit-sequence is a long run of bits of the same value. Another example is a long run of bits of the same value in alternating positions in the bit stream, i.e. in either the odd (O) or even (E) interleave of a bit stream . . . EOEOEO . . . For instance, a long sequence of the form 0a0b0c0d0 . . . , where a, b, c, etc. can be either 0 or 1, would be generally undesirable. Modulation codes impose some form of constraint on the occurrence of undesirable bit-sequences in the encoded bit-stream. For example, some modulation codes impose a so-called j-constraint, whereby the maximum length of a run of consecutive 1's in the encoded bit-stream is limited to the predetermined value j. Other modulation codes impose a constraint on the maximum run-length of consecutive 0's. This is referred to as a k- or G-constraint, whereby the maximum run-length of consecutive 0's is limited to the value k or G respectively. An example of the latter code-type is provided by the PRML (G, I) codes used in PRML (partial-response maximum likelihood) based recording systems such as tape drives and optical storage systems. In addition to the “global” or G-constraint, these codes impose an “interleave” or I-constraint. This limits the maximum run-length of 0's in each of the odd and even interleaves to the value I. An I-constrained bit-stream is of course necessarily G-constrained with G=2I.
Modulation coding systems ideally employ high-rate codes and encoders which operate close to the capacity of the selected constraint. To be useful, however, these systems need to have a practical implementation based on efficient encoding and decoding algorithms.
A practical encoder for imposing a k-constraint in the encoded bit-stream is disclosed in U.S. Pat. No. 5,760,718. This implements an enumerative encoding technique based on the class of generalized Fibonacci codes. Enumerative encoding is discussed in “Enumerative Source Encoding”, T. M. Cover, IEEE Trans. Inform. Theory, Vol. 19, pp. 73-77, January 1973. Fibonacci codes are discussed in “Fibonacci Codes for Synchronisation Control”, W. H. Kautz, IEEE Trans. Inform. Theory, Vol. 11, pp. 284-292, April 1965. While reference is made to the foregoing papers for a detailed discussion, it is useful here to give a brief explanation of these techniques to assist understanding of the invention to be described.
In simple terms, enumerative encoding is a process of mapping input words to output codewords based on lexicographic ordering of the codewords. That is, if a set of X binary codewords are ordered according to binary value, then each codeword can be assigned a number from 1 to X according to its position in the ordered set. If each of these assigned numbers 1 to X then defines the value of a binary input word, each of the X binary input words is associated with a corresponding codeword. Enumerative encoding is the process of mapping input words to output codewords in accordance with this type of scheme. While the underlying encoding principle is simple enough, the problem in practice lies in designing an efficient encoder for generating the codewords from the binary input words. If there are 2100 codewords for example, then the need for an efficient encoder design is readily apparent.
Fibonacci codes are characterised by a set of weights, also called bases, which define the value of a binary 1 at respective positions in a binary codeword representation. That is, a 1 at a given position in a binary codeword represents the value of the Fibonacci weight for that position rather than the usual power of two. As a simple example, consider a Fibonacci code defined by a set of N=7 weights given by {wn: n=1, 2, . . . , 7}={1, 2, 3, 5, 8, 13, 21}. It can be seen that the bases satisfy the linear recursionwn+1=wn+wn−1 for n=2, 3, 6
The complete set of (N=7)-bit Fibonacci codewords can represent wN+1=13+21=34 possible values. Since 34≧25, this simple Fibonacci code can encode 5-bit inputs into codewords of length N=7 by an enumerative encoding process. This encoding process is defined byu=Σxi wN−i+1 for i=1 to 7where u is the input word value and (x1, x2, . . . x7) is the output codeword. The encoding process is performed by successive subtraction of the Fibonacci weights from the input word value as illustrated in FIG. 1 of the accompanying drawings. In particular, the number u is successively reduced by whichever of the weights wn, taken in decreasing value order, does not give a negative result. If a given weight wN−i+1 is actually subtracted from the running difference, then xi=1. Otherwise xi=0.
Consideration of FIG. 1 demonstrates that this simple Fibonacci code imposes a j=1 constraint, i.e. no more than one consecutive 1's can occur in a codeword. Pure Fibonacci codes with a j-constraint are defined by weights wn, n=1, 2, . . . , N, which satisfy the linear recursionwn+1=wn+wn−1+ . . . +wn−j for n=j+1, j+2, . . . , N−1  (1)and the j+1 initial weights are given bywn=2n−1 n=1, 2, . . . , j+1where the specified positive integer j defines the j-constraint of the code. With generalized Fibonacci codes, the equality in equation (1) is replaced by an inequality:wn+1≦wn+wn−1+ . . . +wn−j for n=j+1, j+2, . . . , N−1.  (2)
The maximum number of codewords in such a generalized Fibonacci code is given bywN+1=wN+wN−1+ . . . +wN−j.
As with the simple code of FIG. 1, a binary codeword (x1, x2, . . . , xN) in the generalized Fibonacci code is obtained by representing an input u, 0≦u<wN+1, by the weights {wn}, i. e.u=ΣxiwN−i+1.
For implementation purposes, as described in U.S. Pat. No. 5,760,718 referenced above, the weights are chosen to have a limited span L, i.e.wn=Bn2n−1  (3)where Bn is in the range 2−L≦Bn≦1 and has an L-bit representation. With weights of span L, encoding can be performed in a sliding window fashion, using an (L+1)-bit wide window which runs from the most significant bits of Σuk2k to the least significant bits.
U.S. Pat. No's. 7,126,502, 7,064,687 and 7,071,851 disclose encoders and decoders designed for PRML (G, I) codes which are based on similar enumerative encoding ideas to those of U.S. Pat. No. 5,760,718 referenced above. These are derived from generalized Fibonacci codes. In particular, an input bit-stream is partitioned into its odd and even interleaves, and the two interleave bit-streams are then encoded by separate Fibonacci encoders. Since Fibonacci codes impose a j-constraint on runs of 1's, bit inversion of the encoder outputs results in two encoded bit streams each with a constraint on runs of 0's. A multiplexer then interleaves the encoded bit streams to give a single, (G, I)-constrained bit-stream with G=2I, where I equals the value of j for the original Fibonacci code. In U.S. Pat. No. 7,126,502, the input partitioning stage of the overall encoder is implemented by a demultiplexer. This simply de-interleaves input data words of length 2(N−1) into odd and even interleave sequences of length N−1. In general, if the input sequence of the encoder has an even number of bits, say 2(N−Q), the input can be easily partitioned into two sequences of length N−Q each. An encoder of block length (i.e. output codeword length) 2N and rate (N−Q)/N can then be obtained. To achieve higher rates for the same block length, say a rate (2N−1)/2N for length 2N, it is desirable to partition the input bits into two bit-streams which satisfy certain constraints to be valid input sequences for the subsequent enumerative encoders. In the modulation encoder of U.S. Pat. No. 7,064,687, the input partitioning stage employs a short block encoder to impose such (non-modulation) constraints. Through operation of the short block encoder, the input partitioning stage splits the input into odd and even bit-sequences which satisfy a range constraint. That is, the range of possible values of these N-bit sequences is limited, so that not all possible N-bit sequences can occur. In this way, the possible inputs to the two Fibonacci encoders are limited, allowing N-bit to N-bit encoding in these encoders. The necessary binary constraints on the even and odd bit-sequences are specified for the case where these constraints are the same in the even and the odd interleave, and implementations of short block encoders are given with rates 3/4, 9/10 and 13/14. The construction of these short block encoders for the input partitioning stage is based on the technique of gated partitions. This technique does not provide a systematic approach to the input partitioning problem and, in particular, becomes increasingly difficult to apply for longer and higher rate short block encoders.
In view of the above, it would be desirable to provide an improved technique for the partitioning of input data in modulation coding systems.